package CodeThree;

import java.util.Scanner;
/** @author ASUS */
public class Maxsumofsubarrays {
  public static void main(String[] args) {
    Scanner inputScan = new Scanner(System.in);
    int count = inputScan.nextInt();
    int[] number = new int[count];
    for (int i = 0; i < count; i++) {
      number[i] = inputScan.nextInt();
    }
    int maxSum1 = maxNumber(number);
    int maxSum2 = maxSymbol(number);
    System.out.printf("%d\n%d", maxSum1, maxSum2);
  }

  /** maxSymbol 使用双重循环寻找子数组最大和 */
  private static int maxSymbol(int[] number) {
    // 获取数组长度
    int count = number.length;
    int maxSum = 0;
    for (int i = 0; i < count; i++) {
      int tempSum = 0;
      int tempMax = 0;
      for (int j = i + 1; j < count; j++) {
        tempMax += number[j];
        if (tempMax > tempSum) {
          tempSum = tempMax;
        }
      }
      if (tempSum > maxSum) {
        maxSum = tempSum;
      }
    }
    return maxSum;
  }

  /**
   * maxNumber 使用动态规划寻找子数组最大和
   * tmpSum + num小于num，也就是当前数num之前的数的和是负数的时候，
   * 如果之前的数加起来是负数，没必要把它加上，直接从当前数num开始新的子数组
   * 这种情况下tmpSum = num
   * tmpSum + num大于num，当前数num之前的数加起来是正数，只要之前的tmpSum是正数，
   * 可以增加子数组和的大小，就给加进来。这种情况下tmpSum = tmpSum + num
   */
  private static int maxNumber(int[] number) {
    int maxSum = 0, tmpSum = 0;
    // 使用foreach优化遍历
    for (int num : number) {
      tmpSum = Math.max(tmpSum + num, num);
      maxSum = Math.max(tmpSum, maxSum);
    }
    return maxSum;
  }
}
